package com.yangli.leecode.mashib.interview;

import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @Description
 * @Author liyang
 * @Date 2023/2/17 11:34
 */
public class TwentyTwo {
    public static void main(String[] args) throws ParseException{
        System.out.println(parseDate("2022-12-16 11:26:01","yyyy-MM-dd HH:mm:ss"));


        TwentyTwo twentyTwo = new TwentyTwo();

        System.out.println(twentyTwo.solution(new int[]{4, 1, 3, 2, 3, 9, 5, 5}));
        System.out.println(twentyTwo.trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
        System.out.println(twentyTwo.trap2(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));


    }

    public static Date parseDate(String date,String format){
        try{
            SimpleDateFormat sdf = new SimpleDateFormat(format);
            return sdf.parse(date);
        }catch(Exception e){
            throw new RuntimeException(e);
        }
    }
    //超级洗衣机问题，每个位置表示要洗的衣服数量，最少移动可以使洗衣机平衡，但是每次一个洗衣机只能向两边移动一件衣服
    public int solution(int[] arr){
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int size = arr.length;
        int sum = Arrays.stream(arr).sum();
        if (sum % size != 0) {
            return -1;
        }
        int avg = sum / size;
        int ans = 0;

        int leftSum = 0;
        for (int i = 0; i < size; i++) {
            int leftRest = leftSum - i * avg;
            int rightRest = (sum - leftSum - arr[i]) - (size - i - 1) * avg;
            if (leftRest < 0 && rightRest < 0) {
                ans = Math.max(ans, Math.abs(leftRest + rightRest));
            } else {
                ans = Math.max(ans, Math.max(Math.abs(leftRest), Math.abs(rightRest)));
            }
            leftSum += arr[i];
        }
        return ans;

    }

    //接雨水问题 https://leetcode.cn/problems/trapping-rain-water/
    //暴力方法 遍历数组，当为I时候，求i左边最大数为多少maxL 右边最大数为多少 maxR i可以接的雨水为 Math.min(maxL,maxR)-arr[i]
    //暴力发发优化==>搞两个数组maxL[i] maxR[i]0.。i位左侧最大值，右侧最大值，缓存结果不用每次重复计算了
    public int trap(int[] arr){
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int[] maxL = new int[arr.length];
        int[] maxR = new int[arr.length];

/*        for (int i = 1; i < arr.length; i++) {
            maxL[i] = Math.max(maxL[i - 1], arr[i - 1]);
        }*/
        for (int i = arr.length - 2; i >= 0; i--) {
            maxR[i] = Math.max(maxR[i + 1], arr[i + 1]);
        }
        int ans = 0;
        for (int i = 1; i < arr.length - 1; i++) {
            maxL[i] = Math.max(maxL[i - 1], arr[i - 1]);

            int temp = Math.min(maxL[i], maxR[i]) - arr[i];
            if (temp > 0) {
                ans += temp;
            }
        }
        return ans;
    }

    //还有一种双指针，使空间复杂度由0(N)进一步下降
    public int trap2(int[] arr){
        int ans = 0;
        int max_left = 0;
        int max_right = 0;
        int left = 1;
        int right = arr.length - 2; // 加右指针进去
        while (left <= right) {
            if (arr[left - 1] < arr[right + 1]) {
                max_left = Math.max(max_left, arr[left - 1]);
                if (max_left > arr[left]) {
                    ans += max_left - arr[left];
                }
                left++;
            } else {
                max_right = Math.max(max_right, arr[right + 1]);
                if (max_right > arr[right]) {
                    ans += max_right - arr[right];
                }
                right--;
            }
        }
        return ans;
    }
    //解法 单调栈
    //当前高度小于等于栈顶高度，入栈，指针后移。
    //当前高度大于栈顶高度，出栈，计算出当前墙和栈顶的墙之间水的多少，然后计算当前的高度和新栈的高度的关系，重复第 2 步。直到当前墙的高度不大于栈顶高度或者栈空，然后把当前墙入栈，指针后移


}
